Section: New Results

Rounding-based Moves for Metric Labeling

Paticipants: M. Pawan Kumar

Metric labeling is an important special case of energy minimizaton in Markov random fields. While the best known polynomial-time algorithm for the problem is the linear programming (LP) relaxation, in practice it is slow to solve it. In [25] , we introduced a new family of efficient move-making algorithms for metric labeling. These algorithms mimic the rounding procedues used for converting a fractional LP solution to a feasible integral solution. Our algorithms provide a matching theoretical guarantee to the LP relaxation, while requiring significantly less computational time.